package leetcode.editor.cn;

/**
 * 快速排序https://blog.csdn.net/nrsc272420199/article/details/82587933
 */
public class AQuickSort implements AIOrder{
    @Override
    public void sort(int[] nums) {
        order(nums, 0, nums.length-1);
    }

    private void order(int[] nums, int left, int right) {
        if (left < right) {
            int index = getIndex(nums, left, right);
            order(nums, left, index-1);
            order(nums, index+1, right);
        }
    }

    private int getIndex(int[] nums, int left, int right) {
        if (left < right) {
            int temp = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= temp) {
                    right--;
                }
                nums[left] = nums[right];

                while (left < right && nums[left] <= temp) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = temp;
        }
        return left;
    }

    public static void main(String[] args) {
        AIOrder order = new AQuickSort();
        int[] nums = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        order.sort(nums);
        System.out.println("end");
    }
}
